package dp;

/**
 * Created by fengliejv on 2017/12/6.
 */

public class CoinChange2518 {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount+1];
        dp[0] = 1;
        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j < dp.length; j++) {
                dp[j] += dp[j-coins[i]];
            }
        }
        return dp[dp.length-1];
    }



    //回溯法，超时
//    int count = 0;
//
//    public int change(int amount, int[] coins) {
//        Arrays.sort(coins);
//        backtracing(amount, coins, coins.length - 1);
//        return count;
//    }

//    private void backtracing(int amount, int[] coins, int index) {
//        if(amount==0){
//            count++;
//            return;
//        }
//        if (index < 0) {
//            return;
//        }
//
//        int i = 0;
//        while (amount >= i * coins[index]) {
//            backtracing(amount - i * coins[index], coins, index - 1);
//            i++;
//        }
//    }
}
